\section{Nist Testsuite}
\label{sec_nist}

	In den Tests der implementierten Nist-Testsuite geht es darum herauszufinden ob
	eine Folge von Bits zufällig oder nicht zufällig ist. D.h. ob es in der Folge von
	Bits bestimmte Muster gibt oder ob, mit den gewählten Testmethoden, keine
	Muster zu erkennen sind. Um solche Muster zu erkennen wurden alle Tests so
	ausgelegt, dass sie eine sogenannte null Hypothese (H0) prüfen. Wurde nach
	einem Test die Hypothese erfolgreich bestätigt (H0=true) so geht man davon aus
	das die Folge der Bits zufällig ist. Dazu wird bei jedem Test eine statistische
	Zahl errechnet und mit einer mathematischen Referenz-Verteilung
	verglichen. Übersteigt die errechnete statistische Zahl einen kritischen Wert
	der mathematischen Referenz-Verteilung, so wurde H0 widersprochen, die Bitfolge
	wird als nicht zufällig angesehn. Der kritische Wert wird hierbei so
	gewählt das er möglichst weit abseits der genutzten Verteilung liegt, meist 99
	oder 99,9 Prozent. D.h. der genannte Wert wird in der genutzten Verteilung nur
	sehr selten erreicht. Neben der Hypothese H0 gibt es noch die Hypthese Ha,
	welche besagt das die Folge der Bits nicht zufällig ist. Es wird bei den
	Ergebnissen der Tests zwischen zwei Fehlern Unterschieden:
	
	 \begin{description}
          \item [Typ I Fehler] Der Test hat Ha akzeptiert (Bits nicht zufällig),
          aber die Daten sind zufällig.
          \item [Typ II Fehler] Der Test hat H0 akzeptiert (Bits sind zufällig),
          aber die Daten sind nicht zufällig (weißen ein Muster auf). 
     \end{description}
        
    Alle Test haben als Ziel, die Wahrscheinlichkeit eines Typ II
    Fehlers zu minimieren. So dass also nicht zufällig erzeugte Bits nicht
    fälschlicherweiße als zufällig angesehen werden. Die Wahrscheinlichkeit das
    ein Typ I Fehler auftritt wird mit \(\alpha\) bezeichnet und die
    Wahrscheinlichkeit das ein Typ II Fehler auftritt mit \(\beta\). In den
    implementierten Tests wird \(\alpha\) immer mit 0,01 gewählt. \(\beta\)
    ergibt sich dann aus dem gewählten \(\alpha\) und Größe der Folge von Bits.
    
    \subsection{Maßzahl, Verteilungen und Auswertung}
    \label{subsec_maßzahl}
    Die Tests laufen allgemein immer nach dem gleichen Prinzip ab. Zunächst wird
    eine statistische \textbf{Maßzahl}, der zu testenden Daten, berechnet. Diese
    Maßzahl soll Aufschluss darüber geben wie stark ein bestimmtes Muster oder
    Regelmäßigkeit in den zu prüfenden Daten vorhanden ist, wie diese Zahl zu
    berechnen ist beschreiben dei einzelnen Tests.
    Passend zu dieser Maßzahl gibt es in jedem Test einen Erwartungswert. Dieser Erwartungswert
    würde bei einem, nach NIST, perfektem Zufallszahlengenerator auftreten.
    Zusätzlich zum Erwartungswert gibt es in einen Wert für die Varianz, welcher
    angibt wie stark die Streuung um den Erwartungswert herum ist. Als
    nächstes wird eine bekannte \textbf{Verteilungsfunktion als Referenz} heran
    gezogen. In den Tests wird immer die Standard-Normal-Verteilung oder die
    Chi-Quadrat-Verteilung genutzt. Mit Hilfe der statistischen Maßzahl,
    \textbf{Erwartungswert}, \textbf{Varianz} und der Referenz-Verteilung wird
    der Wert innerhalb der jeweiligen Verteilung berechnet.
    
    \begin{itemize}
      \item \(z = ( x-\mu)/\sigma\) für die Normalverteilung
      \item \(\chi^2 = \sum ((o_i-e_i)^2/e_i)\) für die Chi-Quadrat-Verteilung
    \end{itemize}
    
    Wobei \(x\) und \(o_i\) die errechneten Maßzahlen sind, \(\mu\) und \(e_i\)
    die Erwartungswerte sind und \(\sigma\) die Varianz ist.
    Anschlißend kann mittels dieses Wertes und entweder der Fehlerfunktion
    erfc() oder der Incomplete-Gamma-Function igamc(), der P-Value berechnet
    werden.Innerhalb der Referenz-Verteilung wird ein kritischer Punkt gewählt, 
    welcher mit sehr geringer Wahrscheinlichkeit darin vorhanden ist. Oft wird 
    1 \% oder 0,01 \% gewählt, in unserer Implementierung wurde 1 \% gewählt.
    Der errechnete P-Value hat dann im Wesentlichen 2 Bedeutungen beim Auswerten 
    der Testergebnisse:
    
    \begin{enumerate}
    \item Ist der P-Value beispielsweiße 0,54 so ist die Wahrscheinlichkeit
    54\% dass ein, nach NIST, perfekter Zufallszahlengenerator ein schlechteres
    Ergebnis für diesen Test geliefert hätte. Folglich würde ein P-Value von 1,
    ein perfekt zufälligs Ergebnis bedeuten.
    \item Außerdem bedeutet es, wenn als kritischer Punkt 1 \% gewählt
    wurde und der P-Value gleich 0,54 ist, dass die zu prüfenden Daten mit 99
    prozentiger Sicherheit zufällig sind.
    \end{enumerate} 
	
    \subsection{Programmsteuerung und Ablauf der Tests}
    \label{programm}
    Zur Anzeige alle verfügbaren Programmparameter kann das Programm mit -~-help
    gestartet werden. Ein Programmaufruf um 1 Million Bits mit allen Tests zu
    testen sieht wie folgt aus:\\
    \textbf{./nist\_testsuite -i inputdatei -c 1000000 -a}\
    
    Zu beachten ist, das auf dem System die Boost-Bibliothek installiert sein
    muss \href{https://www.boost.org/}{Boost C++ Libraries}, von dieser werden
    mathematische Funktionen wie die Incomplete-Gamma-Funktion genutzt. (muss
    sie nur zum kompilieren ?)
    
    Vor den Tests wird zunächst die Datei mit den zu prüfenden Zufallsbits
    eingelesen und die Daten in ein Array vom Typ bool umgewandelt. Ist also das
    erste Bit in der Datei eine 1, so hat das Array an der Position 0 den
    Wert true. Anschließend werden alle Tests mit den Testdaten initialisiert,
    d.h. es wird ihnen ein Zeiger auf das Array und die Anzahl der zu testenden
    Bits mitgegeben. Bei der Benutzung ist darauf zu achten, dass die Tests umso
    aussagelkräftiger werden, umso mehr Bits zu testen sind. Bei einer Größe von
    400000 Bits sind die Minimalanforderungen für alle Tests erfüllt, so dass
    diese Größenordnung sehr zu empfehlen ist. Bei zu kleinen Datenmengen kann
    es zu verfälschten Testergebnissen kommen, oder manche Tests werden
    garnicht ausgeführt. Mit dem Parameter \textbf{-o} kann zusätzlich ein
    Offset, in Bytes, beim einlesen der Datei mitgegeben werden. Das ist
    nützlich, da z.B. Chiffren welche durch Openssl erzeugt wurden einen 16
    Byte Offset haben, in denen sonstige Informationen stehen.
	
	
    \subsection{Monobit Test}
    \label{subsec_monobit}
    
    \subsubsection{Zweck des Tests}
    \label{monobit1}
    Im Monobit-Test wird geprüft wie oft eine 1 und wie oft eine 0 in der Folge
    der Bits auftritt. Es wird von einer perfekten Gleichverteilung von 50/50
    ausgegangen, ähnlich der Wahrscheinlichkeit eines Münzwurfs. Im Idealfall
    sollen also immer gleich viele 1er und 0er Bits in der Bitfolge vorkommen,
    der Erwartungwert ist mit 50\% also \(1/2\).
    Als mathematische Referenz-Verteilung wird die Normalverteilung bzw. die
    Halbnormalverteilung genutzt. Über die Fehlerfunktion wird dann der P-Value
    berechnet.
    
    \subsubsection{Implementierung}
    \label{monobit2}
    Für die zu testende Anzahl an Bits <<size>>, wird das gesamte Array
    durchlaufen wobei alle Bits mit 2 multipliziert und anschliessend 1 subtrahiert \(X_i = 2*\epsilon -1\).\\  
    Dabei ist i die momentane Position in der Bitfolge ist und Epsilon den 
    Inhalt der Bitfolge an Position i angibt. Ist das Bit an Position i also eine 1, so
    ist \(X_i = 1\) . Dieser Vorgang wird fuer alle i wiederholt und 
    \(X_i\) aufsummiert zu \(s_n = X_1 + X_2 + \ldots + X_n\). In der
    Implementierung lässt sich das Ganze in 2 Zeilen unterbringen (siehe
    Listing: \ref{lst_monobit} Zeile 1 u. 2). Wenn die Bits perferkt verteilt
    sind so ergibt sich eine Summe \(S_n\) von 0, was dem Erwartungswert
    entspricht. Anschließend wird dieses Summe ins Verhältnis zur Quadratwurzel
    der Anzahl der Bits gesetzt und ergibt den statistischen Wert \(S_o_b_s\).
    Anschließend wird der P-Value errechnet.
    Ist der P-Value < 0.01 so wird gefolgert, dass die Bitfolge zufällig ist,
    ansonsten wird davon ausgegangen dass die Bitfolge nicht zufällig ist. Diese
    Auswertung des P-Value ist für alle folgenden Tests die gleiche. 
    
    
    \lstset{caption={Monobit-Ausschnitt}, label=lst_monobit, language=c++} 
    \begin{lstlisting}
	for (int i = 0; i < size; i++)
		sn += 2*(int)bitArray[i] - 1; 

	sobs = fabs(sn) / sqrt(size);

	p_value = erfc((sobs / sqrt2));
    \end{lstlisting}
     
	
	\subsection{Frequency within a Block Test}
    \label{subsec_frequency}

    
    \subsubsection{Zweck des Tests} 
    \label{frequency1}
    Der Frequency within a Block Test testet innerhalb einer vorgebenen
    Blockgröße die Häufigkeit der vorkommenden 1er Bits. Im Test wird angenommen das die
    perfekte Verteilung innerhalb eines Blockes auch wieder 50 Prozent 1er und
    50 Prozent 0er Bits beträgt. Somit soll verhindert werden, das zwar insgesamt
    die 1en und 0en gleichmäßig verteilt sind und somit der Monobit-Test
    bestanden wird, aber innerhalb vorgegebener Blöcke zuviele 1en oder 0en
    stehen. Beispiel: 0000011111 wäre nicht zufällig laut Nist Testsuite.Die
    Blockgröße M muss so gewählt werden, dass nicht mehr als 100 Blocks
    entstehen, also N < 100. Lässt sich die Anzahl der Bits nicht ganzzahlig
     durch die Anzahl der Blöcke teilen, so werden die letzten Bits verworfen.
    
    
    \subsubsection{Implementierung}
    \label{frequency2}
    Als Eingabeparameter hat man zusätzlich zur Anzahl der zu testenden Bits
    noch die Blockgröße. Aus diesen Eingaben wird die Anzahl der Blöcke
    errechnet <<blockNumber>>. Wie in Listing \ref{lst_frequency} zu sehen
    werden für jeden Block alle 1er Bits zusammengezählt (über explizite
    Typenkonvertierung) und anschließend ins Verhältnis zur Blockgröße gesetzt
    (Zeile 10). Dadurch ergibt sich der Wert \(\pi_i\), was dem prozentualen
    Anteil an 1en im Block entspricht. In Zeile 11 ist zu sehen, dass von jedem
    \(\pi\) der blockinterne Erwartungswert von 50\% abgezogen wird. 
    Als Referenz-Verteilung wird in diesem Test Chi-Quadrat genommen (Zeile 14).
    Zur Überprüfung von des erechneten Wertes in der Verteilung wird die
    Incomplete-Gamma Funktion verwendet.
    
   
    \lstset{caption={Frequency-Ausschnitt}, label=lst_frequency, language=c++} 
    \begin{lstlisting}
	for (int i = 0; i < blockNumber; i++)
	{
		blocksum = 0;
		//sum all ones of a block
		for (int j = 0; j < blockSize; j++)
		{
			blocksum += (int)bitArray[j + i*blockSize];
		}
		//divide the sums of ones through the blocksize
		pi = (double)blocksum / (double)blockSize;
		pi = pi - 0.5;
		pi_sum += (pi*pi);
	}
	chi_squared = 4 * blockSize * pi_sum;

	p_value=boost::math::gamma_q(blockNumber / 2.0, chi_squared / 2.0);
    \end{lstlisting}
    
    
    \subsection{Runs Test}
    \label{subsec_runs}
    
    \subsubsection{Zweck des Tests}
    \label{runs1}
    Im Runs Test wird die längste nicht unterbrochene Folge von
    aufeinanderfolgenden gleichen Bits (0 oder 1). Damit wird für die gesamte
    Bitfolge ermittelt ob die Wechsel zwischen 0 und 1 zu schnell oder zu
    langsam erfolgen.
    
    
    \subsubsection{Implementierung}
    \label{runs2}
    Als Eingabeparameter gibt es hier lediglich wieder die Folge der Zufallsbits
    <<bitArray>> und die Anzahl der zu überprüfenden Bits <<size>>. Zunächst
    wird ähnlich wie im Frequency-Test ein \(\pi\) für alle Einsen berechnet.
    Mit Hilfe dieses Werts wird eine schnelle Prüfung "`checkPi()"' durchgeführt ob
    die Bedingungen des Monobit-Tests erfüllt sind. Anschließend findet der
    eigentliche Runs-Test statt. In Listing \ref{lst_runs} Zeile 3-6 wird immer
    das i-te Bit mit seinem folgnden Bit verglichen. Sind beide Bits gleich, so
    bleibt der Wert \(v_n(obs)\) unverändert. Liegt ein Wechsel von 0 auf 1 oder
    umgekehrt vor, so erhöht sich der Wert um 1. \(v_n(obs)\) bildet also unsere
    statistische Maßzahl. Der Erwartungswert berechnet sich mittels
    \(2*n*\pi*(1-\pi)\) Anschließend über die Fehlerfunktion der P-Value
    berechnet.
    
    \lstset{caption={Runs-Ausschnitt}, label=lst_runs, language=c++} 
    \begin{lstlisting}
	for (int i = 0; i < size-1 ; i++)
	{
		if (bitArray[i] == bitArray[i + 1])
			vn_obs += 0;
		else
			vn_obs += 1;
	}
	vn_obs += 1;
	numerator = std::abs(vn_obs - 2*n*pi*(1-pi));
	denominator = 2 * std::sqrt(2 * n*pi*(1 - pi));
	p_value = std::erfc(numerator/denominator);
    \end{lstlisting}
    
    
    \subsection{Longest Run of Ones Test}
    \label{subsec_longestrun}
    
    \subsubsection{Zweck des Tests}
    \label{longestrun1}
    Im Longest Run of Ones Test geht es ähnlich wie im Runs Test darum, die
    längste aufeinanderfolgdene Sequenz von Einsen zu ermitteln. Allerdings wird
    die gesamte Bitfolge in Blöcke eingeteilt. Die Größe der Blöcke hängt von
    der Anzahl der zu prüfenden Bits ab, wobei ab einer Anzahl von n=750000 Bits
    die Blockgröße auf M=10000 festgelegt ist. Je mehr Bits zu prüfen sind, umso
    größer werden die Blöcke und umso mehr Klassen K gibt es. Die Klassen geben
    an wie groß die Wahrscheinlichkeit ist eine bestimmte Länge von
    aufeinanderfolgenden Einsen in einem Block vorzufinden. Wie genau die
    Blockgröße festgelegt ist oder wie sich die Wahrscheinlichkeit der einzelnen
    Klasse errechnet ist aus dem NIST Dokument nicht ersichtlich. Hier wird auf
    ein Dokument von Pal Revesz, Random Walk in Random and Non-Random
    Enviroments, verwießen.
    
    
    \subsubsection{Implementierung}
    \label{longestrun2}
    Da uns nur das NIST-Dokument vorliegt wurden die beschriebenen Tabellen der
    Blockgrößen und Wahrscheinlichkeiten der Klassen über ein Array von Structs
    abgebildet <<v[]>>. Dabei ist  das Struct vom Typ <<v\_class>> und besteht
    aus:
    
    \begin{description}
          \item [value] Anzahl aufeinanderfolgender Einsen in dieser Klasse.
          \item [count] Gibt an wieviele Blöcke in diese Klasse fallen.
          \item [pi] Gibt die Wahrscheinlichkeit an, dass ein Block in diese
          Klasse fällt.
     \end{description}
     
    Anhand der Anzahl der zu überprüfenden Bits wird die Blockgröße und damit
    die Klasseneinteilung vorgenommen, die Structs in dem Array werden
    dementsprechend initialisiert und ihre Counter auf 0 gesetzt. Nun wird für
    jeden Block die längste Folge von aufeinanderfolgenden Einsen ermittelt und
    der die count-Variable im entsprechenden Struct erhöht. Anschließend wird
    Chi-Quadrat mit Hilfe der Counter und der Wahrscheinlichkeit der Klassen
    berechnet (siehe Listing \ref{lst_longestruns} Zeile 3-5) und über die
    Incomplete-Gamma-Function der P-Value gebildet. 
    
    \lstset{caption={Longest Runs of Ones in a Block-Ausschnitt},
    label=lst_longestruns, language=c++}
    \begin{lstlisting}
	for (int i = 0; i < numberOfClasses; i++)
	{
		numerator = (v[i].count - numberOfblocks*v[i].pi);
		denominator = numberOfblocks * v[i].pi;
		chi_sqr += ((numerator*numerator) / denominator);
	}
	p_value = boost::math::gamma_q((numberOfClasses)/2, chi_sqr / 2);
    \end{lstlisting}
    
    
    \subsection{Binary Matrix Test}
    \label{subsec_matrix}
    
    \subsubsection{Zweck des Tests}
    \label{matrix1}
    Beim Binary-Matrix Test geht es darum innerhalb gleichlanger Substrings, der
    Zufallsfolge von Bits, lineare Abhängigkeiten zu finden. Dabei wird die
    gesamte Folge von Bits in gleichgroße quadratische Matrizen eingeteilt.
    Danach wird von jeder Matrix der Rang bestimmt, wozu ein binärer
    Gauß-Algorithmus einmal vorwärts und rückwärts durchgeführt wird.
    
    \subsubsection{Implementierung}
    \label{matrix2}
    Die Größe der Matrizen ist in unserer Implementierung, wie in der
    Beispielimplementierung von Nist, auf 32 festgelegt. Als minimale
    Eingabelänge für diesen Test werden also 38,912 Bits benötigt. Zunächst
    wird die Anzahl der Matrizen ermittelt. Diese werden Zeile für Zeile mit den
    aufeinander folgenden Bits aus dem Bitarray befüllt. D.h. die erste 32 Bit
    stehen in Zeile 1 von Matrix 1, Bit 33 bis 64 stehen in Zeile 2 von Matrix 1
    usw.. Allgemein wird ein Rang einer Matrix dadurch bestimmt wieviele Zeilen
    noch eine 1 nach dem Durchlaufen des Gauss Algorithmus haben. Insgesamt gibt
    es immer 3 Klassen:
    
    \begin{description}
          \item [FM] Full Rank : P= 0.2888
          \item [FM-1] Full Rank -1 : P = 0.5776
          \item [N-FM] All Remaining Matrices : P = 0.1336
     \end{description}
     
     Wobei P die erwartete Wahrscheinlichkeit ist mit der eine Matrix der größe
     32x32 den entsprechenden Rang hat, vorausgesetzt die Daten sind zufällig.
     Über die Anzahl der Matrizen eines Ranges und dessen erwarteter
     Wahrscheinlichkeit wird der Chi-Quadrat Wert berechnet. Dieser wird wieder
     mit der Incomplete-Gamma-Funktion ausgewertet, wordurch der P-Value
     errechnet wird.
    
 
    
    \subsection{Maurers Universal Test}
    \label{subsec_universal}
    
    
    \subsubsection{Zweck des Tests}
    \label{universal1}
    Bei Maurers Universal Test geht es darum, herauszufinden ob sich eine Folge
    von Zufallsbits so kompirmieren lässt, dass es keinen Informationsverlust
    gibt. Ist das möglich, so kann angenommen werden, dass die Folge nicht
    zufällig ist.
    
    \subsubsection{Implementierung}
    \label{universal2}
    Für die Ausführung des Tests, muss die zu prüfende Bitfolge zunächst in
    Blöcke der Größe L eingeteilt werden. Dabei is L abhängig von der Länge der
    Folge bzw. der Menge zu prüfender Bits. Wie diese in Zusammenhang stehen
    lässt sich in \cite{NIST} auf Seite 45 unter 2.9.7 ersehen. Außerdem wird
    dort auf die Dimensionierung von Q und K eingegangen. Die dort abgebildete
    Tabelle wurde im Programm als if/else Verzweigung implementiert.
    Zunächst wird die Folge also in Blöcke der Größe L eingeteilt. Dabei werden
    Q viele Blocks zur Initialisierung und K viele Blocks zum Testen verwendet. 
    Für jede mögliche Bitkombination eines L langen Blocks muss nun eine
    Variable bereit gestellt werden. Wenn die zu prüfenden Folge z.B. 1 Mio Bits
    lang ist, so ist L = 7. Somit gibt es \(2^7 = 128\) verschiedene
    Bitkombinationen. Das Array "`table[]"' entspricht dieser Größe. Über eine
    Hilfsfunktion "`binToDec()"' wird ein Block der Länge L in eine Dezimalzahl
    umgewandelt. Das Array "`table[]"' an der Stelle der errechneten Dezimalzahl
    auf die Blocknummer gesetzt, welche dem Zähler i der Schleife entspricht
    (siehe Lst.: \ref{lst_inituniversal} Zeile 3 und 4).
    
    \lstset{caption={Initialisierung Universal Test},
    label=lst_inituniversal, language=c++}
    \begin{lstlisting}
	for (int i = 0; i < numberOfInitBlocks; i++)
	{
		tempValue = binToDec(i*blocklength);
		table[tempValue] = i;
	}
    \end{lstlisting}
    
    Als nächstes wird der eigentliche Test gestartet. Hierbei wird wieder jeder
    der K Blocks mit Hilfe der Funktion "`binToDec()"' in die netsprechende
    Dezimalzahl gewandelt (Listing \ref{lst_universal} Zeile 3). Danach wird die
    Nummer des Blockes ermittelt, welcher als letztes diese Zahl (Bitkombination)
    hatte. Kam die Bitkombination nicht in den Initialblöcken vor, so ist der
    Wert 0. Anschließend wird die Distanz zwischen den beiden wiederkehrenden
    Bitkombinationen in der Varialbe "`sum"' gespeichert und im Array "`table"'
    die Nummer des momentanen Blocks gepspeichert. Wurde dies mit jedem der K
    Blöcke getan, so wird die Summe aller Distanzen von wiederkehrenden
    Bitkombination ins Verhältnis zu der Anzahl der zu testenden Blöcke K
    gesetzt (Listing \ref{lst_universal} Zeile 8).
    
    \newpage 
     \lstset{caption={Universal Test},
    label=lst_universal, language=c++}
    \begin{lstlisting}
	for (int i = numberOfInitBlocks; i < numberOfInitBlocks + numberOfTestBlocks; i++)
	{
		tempValue = binToDec(i*blocklength);
		lastBlock = table[tempValue];
		sum += std::log(i - lastBlock) / std::log(2);
		table[tempValue] = i;
	}
	fn = sum / numberOfTestBlocks;
    \end{lstlisting}
    
   Anschließend wird der P-Value mittels der komplementären Fehlerfunktion
   berechnet. Dabei wird unserer errechneter Wert "`fn"' mit einem
   Erwartungswert verrechnet. Dieser Eewartungswert hängt von der Blockgröße L
   ab und ist in \cite{NIST} Seite 44 beschrieben. Außerdem muss eine Abweichung
   mit einberechnet werden, welche zuvor über K und L errechnet wird. 
     
    
    \subsection{Linear Complexity Test}
    \label{subsec_linear}
    
    \subsubsection{Zweck des Tests}
    \label{linear1}
    Beim Linear Complexity Test wird die zu prüfende Folge wieder in Blöcke der
    Länge M aufgeteilt. Der Test soll feststellen wie komplex
    ein linear feedback shift register (LFSR) für die einzelnen Blöcke ist. Bei
   Blöcken mit zufälliger Bitfolge werden komplexe, also lange, LFSR's erwartet.
   Wohingegen zu kurze (nicht komplexe) LFSR's auf eine nicht zufällige Folge
   hinweisen.
    
    \subsubsection{Implementierung}
    \label{linear2}
    Als Eingabe wird bei diesem Test eine minimal Bitlänge von 1
    Million Bits empfohlen, wobei die Blockgröße zwischen 500 und 5000 liegen
    sollte. Ansonsten kann es sein das das Ergebnis keine Aussagekraft besitzt.
    Im Allgemein besteht die Implementierung zum größten Teil in der
    Implementierung des Berkley-Massey Algorithmus (siehe auch \cite{BM}),
    welcher die Länge des LFSR für einen Block der Länge M aus der zu prüfenden
    Bitfolge berechnet. Anhand der Länge des LFSR eines Blockes lässt sich der
    Block einer Klasse \(v_0\) bis \(v_6\) zuordnen, wie sie in \cite{NIST} auf
    Seite 47 beschrieben sind. Anschließend wird über die Anzahl der Blöcke in
    den einzelnen Klassen und dazugehörigen Erwartungswerten, der Wert der
    Chi-Quadrat Verteilung berechnet. Zur Berechnung des P-Value wird wieder die
    Incomplete-Gamma-Function genutzt.
    
    
    
       
        
    
       


